package Review;


public class Test17 {

	public static void main(String[] args) {
		ListNode p1 = new ListNode(1);
		ListNode p2 = new ListNode(1);
		ListNode p3 = new ListNode(5);
		ListNode p4 = new ListNode(7);
		p1.next=p2;
		p2.next=p3;
		p3.next=p4;
		p4.next=null;
		ListNode p5 = new ListNode(2);
		ListNode p6 = new ListNode(4);
		ListNode p7 = new ListNode(6);
		ListNode p8 = new ListNode(8);
		p5.next=p6;
		p6.next=p7;
		p7.next=p8;
		p8.next=null;
		ListNode p = merge(p1,p5);
		while(p!=null)
		{
			System.out.print(p.value);
			p=p.next;
		}
	}
    public static ListNode merge(ListNode head1,ListNode head2){
    	if(head1==null){
    		return head2;
    	}
    	if(head2==null){
    	return head1;
    	}
    	ListNode newHead=null;
    	if(head1.value<=head2.value){
    		newHead=head1;
    		newHead.next=merge(head1.next, head2);
    	}
    	else{
    		newHead=head2;
    		newHead.next=merge(head1, head2.next);
    	}
    	return newHead;
    }
}
